#ifndef _MATH_EXPRESSION_SHANFL_H
#define _MATH_EXPRESSION_SHANFL_H
#include <map>
#include <string>
#include <vector>
#include <deque>
#include <iostream>

/*
    // demo1
    MathExpr::MathExpression math2;
    math2.add_var("x1", 1);
    math2.add_var("x2", 2);
    math2.add_var("x3", 1);
    math2.add_var("x4", 2);
    math2.add_var("x5", 1);
    math2.add_var("x6", 2);
    math2.add_var("y1", 1);
    math2.add_var("y2", 2);
    math2.add_var("y3", 1);
    math2.add_var("y4", 2);
    math2.add_var("y5", 1);
    math2.add_var("y6", 2);
    double v =
   math2.eval("3.1415926/6*sqrt((x1-x2)^2+(y1-y2)^2)*sqrt((x3-x4)^2+(y3-y4)^2)*sqrt((x5-x6)^2+(y5-y6)^2)").second;
*/

namespace MathExpr {
    static const double E = 2.718281828459045;

    enum TType
    {
        NONE,
        NAME,
        SEP,
        OP,
        NUMBER,
    };

    struct Token
    {
        std::string str;
        double value = 0;
        TType type;
        int needParamNum = 1; // 例如 max()函数支持任意多个参数

        Token(TType t, char c)
        {
            str = c;
            type = t;

            if (t == NUMBER)
            {
                if (c == 'E')
                {
                    value = E;
                }
                else
                {
                    value = atof(str.c_str());
                }
            }
        }

        Token(TType t, std::string c)
        {
            str = c;
            type = t;

            if (t == NUMBER)
            {
                if (str[str.length() - 1] == 'E')
                {
                    if (str == "-E")
                    {
                        value = -E;
                    }
                    else
                    {
                        value = E * atof(str.substr(0, str.length() - 1).c_str());
                    }

                    // TODO:
                    // -.E   --- > 这是不对的,目前辨别成本较高.
                }
                else
                {
                    value = atof(str.c_str());
                }
            }
        }

        Token(double d)
        {
            str = "";
            value = d;
            type = NUMBER;
        }

        bool IsOp()
        {
            return type == OP;
        }

        bool IsOP_POWER()
        {
            return IsOp() && str == "^";
        }
    };

    using FN1 = double(*)(double);
    using FN2 = double(*)(std::vector<double> params);

    double Cpow(std::vector<double> params)
    {
        if (params.size() < 2)
        {
            return nanf("");
        }

        double v1 = params[0];
        double v2 = params[1];
        return std::pow(v1, v2);
    }

    double Cavg(std::vector<double> params)
    {
        double res = nanf("");
        if (!params.empty())
        {
            int count = params.size();
            double sumValue = 0;
            for (auto tmpV : params)
            {
                sumValue += tmpV;
            }
            res = sumValue / count;
        }

        return res;
    }

    double Cmax(std::vector<double> params)
    {
        double res = nanf("");
        if (!params.empty())
        {
            res = params[0];
            for (auto tmpV : params)
            {
                if (res < tmpV)
                {
                    res = tmpV;
                }
            }
        }

        return res;
    }


    double Cmin(std::vector<double> params)
    {
        double res = nanf("");
        if (!params.empty())
        {
            res = params[0];
            for (auto tmpV : params)
            {
                if (res > tmpV)
                {
                    res = tmpV;
                }
            }
        }

        return res;
    }

    double Csin(std::vector<double> params)
    {
        double res = nanf("");
        if (!params.empty())
        {
            res = std::sin(params[0]);
        }

        return res;
    }

    double Cfabs(std::vector<double> params)
    {
        double res = nanf("");
        if (!params.empty())
        {
            res = std::fabs(params[0]);
        }

        return res;
    }

    double Cacos(std::vector<double> params)
    {
        double res = nanf("");
        if (!params.empty())
        {
            res = std::acos(params[0]);
        }

        return res;
    }

    double Casin(std::vector<double> params)
    {
        double res = nanf("");
        if (!params.empty())
        {
            res = std::asin(params[0]);
        }

        return res;
    }

    double Catan(std::vector<double> params)
    {
        double res = nanf("");
        if (!params.empty())
        {
            res = std::atan(params[0]);
        }

        return res;
    }

    double Ccos(std::vector<double> params)
    {
        double res = nanf("");
        if (!params.empty())
        {
            res = std::cos(params[0]);
        }

        return res;
    }

    double Cexp(std::vector<double> params)
    {
        double res = nanf("");
        if (!params.empty())
        {
            res = std::exp(params[0]);
        }

        return res;
    }

    double Cfloor(std::vector<double> params)
    {
        double res = nanf("");
        if (!params.empty())
        {
            res = std::floor(params[0]);
        }

        return res;
    }

    double Clog(std::vector<double> params)
    {
        double res = nanf("");
        if (!params.empty())
        {
            res = std::log(params[0]);
        }

        return res;
    }

    double Clog10(std::vector<double> params)
    {
        double res = nanf("");
        if (!params.empty())
        {
            res = std::log10(params[0]);
        }

        return res;
    }

    double Csqrt(std::vector<double> params)
    {
        double res = nanf("");
        if (!params.empty())
        {
            res = std::sqrt(params[0]);
        }

        return res;
    }

    double Ctan(std::vector<double> params)
    {
        double res = nanf("");
        if (!params.empty())
        {
            res = std::tan(params[0]);
        }

        return res;
    }

    class MathExpression
    {
    public:

        MathExpression(std::map<std::string, double> otherItems = {})
        {
            add_fn1("abs", Cfabs);
            add_fn1("acos", Cacos);
            add_fn1("asin", Casin);
            add_fn1("atan", Catan);
            add_fn1("cos", Ccos);
            add_fn1("exp", Cexp);
            add_fn1("floor", Cfloor);
            add_fn1("ln", Clog);
            add_fn1("log", Clog10);
            add_fn1("LOG", Clog10);
            add_fn1("sin", Csin);
            add_fn1("sqrt", Csqrt);
            add_fn1("tan", Ctan);
            add_fn1("pow", Cpow);
            add_fn1("avg", Cavg);
            add_fn1("max", Cmax);
            add_fn1("min", Cmin);

            add_var("pi", 3.141592653589793);
            add_var("M_PI", 3.141592653589793);

            for (auto item : otherItems)
            {
                add_var(item.first, item.second);
            }
        }

        void add_fn1(std::string name, FN2 fn)
        {
            m_FN1_map[name] = fn;
        }

        std::pair<bool, double> eval(std::string mathexpr_str)
        {
            // clear_var();
            m_tokens.clear();
            m_OperatorStack.clear();
            m_RPN.clear();

            int pos = mathexpr_str.find("EXP(", 0);
            if (pos > -1)
            {
                mathexpr_str.replace(pos, 4, "exp(");
            }

            Parser(mathexpr_str);
            this->InfixToRPN();
            double v = 0;
            bool b = this->RPNToDouble(v);
            return std::make_pair(b, v);
        }

        void clear_var()
        {
            m_vars.clear();
        }

        void add_var(std::string varname, double value)
        {
            m_vars[varname] = value;
        }

        void RPN_Print()
        {
            for (auto& it : m_RPN)
            {
                std::cout << it.str << " ";
            }
            std::cout << "\n";
        }

    protected:
        bool Parser(std::string str)
        {
            // std::vector<Token> ret;
            TType type = NONE;
            std::string name;
            int TotalLen = str.length();
            for (int i = 0; i < str.length(); i++)
            {
                char c = str[i];
                switch (type)
                {
                case NONE:
                    switch (c)
                    {
                    case '+':
                        // case '-':
                    case '/':
                    case '*':
                    case '^':
                    {
                        m_tokens.push_back({ OP, c });
                    }
                    break;
                    case '-':
                    {
                        // -E-23
                        // -3E+2
                        // (-E-3)
                        // -.3e4
                        // 2-3
                        if (m_tokens.size() == 0 || m_tokens[m_tokens.size() - 1].str == "(" ||
                            m_tokens[m_tokens.size() - 1].str == "^" || m_tokens[m_tokens.size() - 1].type == OP)
                        {
                            // 数字
                            name = c;
                            type = NUMBER;
                        }
                        else
                        {
                            m_tokens.push_back({ OP, c });
                        }
                    }
                    break;

                    case '(':
                    case ')':
                    case ',':
                        m_tokens.push_back({ SEP, c });
                        break;
                    default:
                        if ((c >= '0' && c <= '9') || c == '.' || c == '-')
                        {
                            type = NUMBER;
                            name = c;
                        }
                        else if (c == 'E')
                        {
                            bool isFounVariable = false;
                            for (auto& it : m_vars)
                            {
                                std::string vname = it.first;
                                std::string willname = str.substr(i, vname.length());
                                if (vname.compare(willname) == 0)
                                {
                                    isFounVariable = true;
                                    type = NONE;
                                    m_tokens.push_back({ NAME, vname });
                                    i += vname.length();
                                    i--;
                                    break;
                                }
                            }

                            if (isFounVariable)
                                break;

                            type = NONE;
                            m_tokens.push_back({ NUMBER, c });
                        }
                        else if (isalpha(c))
                        {
                            // 是否是变量
                            // 是否是内置函数
                            bool isFounVariable = false;
                            for (auto& it : m_vars)
                            {
                                std::string vname = it.first;
                                std::string willname = str.substr(i, vname.length());
                                if (vname.compare(willname) == 0)
                                {
                                    if (i + vname.length() > TotalLen)
                                    {
                                        continue;
                                    }
                                    else
                                    {
                                        char ccc = str[i + vname.length()];
                                        if (ccc == '*' || ccc == '+' || ccc == '-' || ccc == '/' || ccc == '^' ||
                                            ccc == '(' || ccc == ')' || ccc == ',' || ccc == '\0')
                                        {
                                            isFounVariable = true;
                                            type = NONE;
                                            m_tokens.push_back({ NAME, vname });
                                            i += vname.length();
                                            i--;
                                            break;
                                        }
                                    }
                                }
                            }

                            if (isFounVariable)
                                break;
                            else
                            {
                                type = NAME;
                                name = c;
                            }
                        }
                    }
                    break;
                case NUMBER:
                {
                    if (c == 'E')
                    {
                        // 4E*1.33
                        // 这里4E作为一个数字
                        name.append(1, c);
                        m_tokens.push_back({ NUMBER, name });
                        type = NONE;
                    }
                    else if ((c >= '0' && c <= '9') || c == '.' || c == 'E' || (c == '-' && str[i - 1] == 'E'))
                    {
                        name.append(1, c);
                    }
                    else
                    {
                        type = NONE;
                        m_tokens.push_back({ NUMBER, name });
                        i--;
                    }
                }
                break;
                case NAME:
                {
                    if (isalnum(c))
                    {
                        name.append(1, c);
                    }
                    else
                    {
                        m_tokens.push_back({ NAME, name });
                        i--;
                        type = NONE;
                    }
                }
                break;
                }
            }

            if (type != NONE)
                m_tokens.push_back({ type, name });

            handleMinus();
            return true;
        }

        // 单纯的 - 负号转为 -1 *
        void handleMinus()
        {
            while (true)
            {
                bool findRes = false;
                std::vector<Token>::iterator iter = m_tokens.begin();
                for (; iter != m_tokens.end(); iter++)
                {
                    if (iter->str == "-" && iter->type == NUMBER)
                    {
                        findRes = true;
                        break;
                    }
                }

                if (findRes)
                {
                    iter = m_tokens.insert(iter, { OP, "*" });
                    iter = m_tokens.insert(iter, { NUMBER, "-1" });
                    m_tokens.erase(iter + 2);
                }
                else
                {
                    break;
                }
            }
        }

        bool InfixToRPN()
        {
            std::vector<int> needParamNumStack;
            for (int i = 0; i < m_tokens.size(); i++)
            {
                char op;
                Token tk = m_tokens[i];
                switch (tk.type)
                {
                case NUMBER:
                    m_RPN.push_back(tk);
                    break;
                case SEP:
                {
                    if (tk.str == "(")
                    {
                        needParamNumStack.push_back(1);
                        m_OperatorStack.push_back(tk);
                    }
                    else if (tk.str == ",")
                    {
                        if (needParamNumStack.size() > 0)
                        {
                            needParamNumStack[needParamNumStack.size() - 1] = needParamNumStack[needParamNumStack.size() - 1] + 1;
                        }
                    }
                    else
                    {
                        if (m_OperatorStack.size() == 0)
                            return false;

                        while (!(m_OperatorStack.back().type == SEP && m_OperatorStack.back().str == "("))
                        {
                            m_RPN.push_back(m_OperatorStack.back());
                            m_OperatorStack.pop_back();

                            if (m_OperatorStack.size() == 0)
                                return false;
                        }
                        m_OperatorStack.pop_back();
                        // 左括号前面是函数，则连同左括号一起弹出
                        if (m_OperatorStack.size() && IsFunction(m_OperatorStack.back()))
                        {
                            Token tmpFunc = m_OperatorStack.back();
                            if (needParamNumStack.size() > 0)
                            {
                                tmpFunc.needParamNum = needParamNumStack[needParamNumStack.size() - 1];
                            }
                            m_RPN.push_back(tmpFunc);
                            m_OperatorStack.pop_back();
                        }
                        if (needParamNumStack.size() > 0)
                        {
                            needParamNumStack.pop_back();
                        }
                    }
                }
                break;
                case OP:
                {
                    while (m_OperatorStack.size() && m_OperatorStack.back().IsOp())
                    {
                        if (precedence(tk) <= precedence(m_OperatorStack.back()))
                        {
                            m_RPN.push_back(m_OperatorStack.back());
                            m_OperatorStack.pop_back();
                        }
                        else
                        {
                            break;
                        }
                    }
                    m_OperatorStack.push_back(tk);
                    // 2^3^4 => 2^(3^4)
                    // 2*3*3^4
                    //if (tk.IsOP_POWER())
                    //{
                    //    // ^ 是 右结合的 这里直接放到operator stack 中.
                    //    m_OperatorStack.push_back(tk);
                    //}
                    //else
                    //{
                    //    while (m_OperatorStack.size() && m_OperatorStack.back().IsOp())
                    //    {
                    //        if (precedence(tk) <= precedence(m_OperatorStack.back()))
                    //        {
                    //            m_RPN.push_back(m_OperatorStack.back());
                    //            m_OperatorStack.pop_back();
                    //        }
                    //        else
                    //        {
                    //            break;
                    //        }
                    //    }
                    //    m_OperatorStack.push_back(tk);
                    //}
                }
                break;

                case NAME:
                {
                    if (i == m_tokens.size() - 1 || m_tokens[i + 1].str != "(")
                    {
                        m_RPN.push_back(tk);
                    }
                    else
                    {
                        m_OperatorStack.push_back(tk);
                    }
                }
                break;
                }
            }

            while (m_OperatorStack.size())
            {
                m_RPN.push_back(m_OperatorStack.back());
                m_OperatorStack.pop_back();
            }

            return true;
        }

        bool IsZeroFloat(float f)
        {
            return fabs(f) < FLT_EPSILON;
        }

        bool RPNToDouble(double& v)
        {
            std::deque<Token> stack;
            for (int i = 0; i < m_RPN.size(); i++)
            {
                Token tk = m_RPN[i];

                if (IsNumber(tk))
                {
                    stack.push_back(tk);
                }
                else if (IsVariable(tk))
                {
                    tk.value = m_vars[tk.str];
                    stack.push_back(tk);
                }
                else if (IsFunction(tk))
                {
                    // FN1 fn = m_FN1_map[]
                    if (stack.size() == 0)
                        return false;

                    std::vector<double> realParams;
                    for (int i = 0; i < tk.needParamNum; i++)
                    {
                        if (stack.size() > 0)
                        {
                            Token stackTk = stack.back();
                            stack.pop_back();
                            realParams.insert(realParams.begin(), stackTk.value);
                        }
                        else
                        {
                            break;
                        }
                    }
                    double v = m_FN1_map[tk.str](realParams);
                    stack.push_back(Token(v));
                }
                else if (IsOp(tk))
                {
                    if (stack.size() < 2)
                        return false;
                    double d1 = stack.back().value;
                    stack.pop_back();
                    double d2 = stack.back().value;
                    stack.pop_back();

                    double d = 0;
                    if (tk.str == "+")
                        stack.push_back(Token(d1 + d2));
                    else if (tk.str == "-")
                        stack.push_back(Token(d2 - d1));
                    else if (tk.str == "*")
                        stack.push_back(Token(d2 * d1));
                    else if (tk.str == "/") // todo: /0 ?
                    {
                        if (this->IsZeroFloat(d1))
                            return false;

                        stack.push_back(Token(d2 / d1));
                    }

                    else if (tk.str == "^")
                        stack.push_back(Token(pow(d2, d1)));
                }
                else
                {
                    //
                    std::cout << "[error] type:" << tk.type << ", str = " << tk.str << std::endl;
                    return false;
                }
            }

            if (stack.size() != 1)
                return false;

            v = stack.back().value;
            return true;
        }

        // --
        inline int precedence(const Token& o)
        {
            if (o.str == "+" || o.str == "-")
                return 1;
            else if (o.str == "*" || o.str == "/")
                return 2;
            else if (o.str == "^")
                return 3;
            else if (IsFunction(o))
                return 999;
            else
                return 4;
        }

        bool IsFunction(Token& tk)
        {
            return tk.type == NAME && m_FN1_map.find(tk.str) != m_FN1_map.end();
        }

        bool IsFunction(const Token& tk)
        {
            return tk.type == NAME && m_FN1_map.find(tk.str) != m_FN1_map.end();
        }

        bool IsVariable(Token& tk)
        {
            return tk.type == NAME && m_vars.find(tk.str) != m_vars.end();
        }

        bool IsOp(Token& tk)
        {
            return tk.IsOp();
        }

        bool IsNumber(Token& tk)
        {
            return tk.type == NUMBER;
        }

    private:
        std::map<std::string, double> m_vars;
        std::vector<Token> m_tokens;

        std::deque<Token> m_OperatorStack;
        std::deque<Token> m_RPN;
        //std::map<std::string, FN1> m_FN1_map;
        std::map<std::string, FN2> m_FN1_map;
    };
} // namespace MathExpr

#endif // PARSERMATH_H
